//
// Created by SXL on 2025/8/27.
//
#include "simulate.hpp"
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <cmath>
using namespace  std;


//https://codefun2000.com/p/P2370  hash4 stoull转unsigned long long
void hash4() {
    int n;
    cin>>n;
    set<int> a;
    while (n--) {
        int temp;
        cin>>temp;
        a.insert(temp);

    }

    int m;
    cin>>m;
    getchar();
    vector<pair<string,set<int>>> arr;
    while (m--) {
        string line ;
        getline(cin,line);
        stringstream ss(line);
        string token;
        string name;
        getline(ss,name,' ');
        pair<string,set<int>> temp;
        temp.first =name;
        temp.second = set<int>();
        getline(ss,token,' ');
        while (getline(ss,token,' ')) {
            temp.second.insert(stoi(token));
        }
        arr.push_back(temp);
    }
    vector<unsigned long long> ans;
    // for ( auto port:a) {
    //     for (auto node :arr) {
    //         if (node.second.count(port)) {
    //             ans.push_back(node.first);
    //             // for (auto ip:node.second) {
    //             //     a.insert(ip);
    //             // }
    //         }
    //     }
    // }

    for (auto node :arr) {
        for (auto port :a) {
            if (node.second.count(port)) {
                ans.push_back(stoull(node.first));
                break;
            }
        }
    }
    cout<<ans.size()<<endl;
    sort(ans.begin(),ans.end());
    // erase(unique(ans.begin(),ans.end()),ans.end());
    for (const auto& res:ans) {
        cout<<res<<" ";
    }

}

//https://codefun2000.com/p/P2313  hash 数组消除   直接比超时，注意性质 同余数

void hahs4() {
    int n;
    cin>>n;
    vector<ll> arr(n);
    ll max_num=0;
    for (int i=0;i<n;i++) {
        cin>>arr[i];
    }
    int inter;
    cin>>inter;

    map<ll,vector<ll>> mp;
    for (auto num:arr) {
        mp[num%inter].push_back(num);
    }

    ll maxsum=0;
    ll minele=-1;
    for (auto list:mp) {
        if (list.second.size()==maxsum) {
            sort(list.second.begin(),list.second.end());
            if (list.second[0]<minele) {
                maxsum=list.second.size();
                sort(list.second.begin(),list.second.end());
                minele= list.second[0];
            }
        }
        if (list.second.size()>maxsum) {
            maxsum=list.second.size();
            sort(list.second.begin(),list.second.end());
            minele= list.second[0];
        }
    }
    cout<<minele;
}

//https://codefun2000.com/p/P2309   分层存储 位移算层 map<int(层),map<key,num>>  map转vector<pair<int,int>> cmp仿函数

void hash5() {
    int n;
    cin>>n;
    int cnt=0;
    int ceng=1;
    map<int,map<int,int>> mp;
    while (n--) {
        int temp;
        cin>>temp;
        if (cnt<(1<<ceng)-1) {
            mp[ceng][temp]++;
            cnt++;
        }else {
            ceng++;
            mp[ceng][temp]++;
            cnt++;
        }

    }
    int originceng=ceng;
    cin>>n;
    cnt=0,ceng=1;
    map<int,map<int,int>> mp2;
    while (n--) {
        int temp;
        cin>>temp;
        if (cnt<(1<<ceng)-1) {
            mp2[ceng][temp]++;
            cnt++;
        }else {
            ceng++;
            mp2[ceng][temp]++;
            cnt++;
        }

    }
    int referceng=ceng;
    for (int i=1;i<=originceng&&i<=referceng;i++) {
        for (auto &origin:mp[i]) {
            if (mp2[i].count(origin.first)) {
                origin.second-=mp2[i][origin.first];

            }
        }
    }
    unordered_map<int,int> ans;
    for (int i=1;i<=mp.size();i++) {
        // cout<<"the"<<i<<"ceng "<<endl;
        for (auto node:mp[i]) {
            if (node.second>0) {
                if (!ans.count(node.first)) {
                    ans.insert(node);
                }else {
                    ans[node.first]+=node.second;
                }
            }
            // cout<<node.first<<" "<<node.second<<endl;;
        }
    }
    // cout<<endl;
    vector<pair<int,int>> res;
    for (auto it =ans.begin();it!=ans.end();it++) {
        res.push_back(*it);
    }
    sort(res.begin(),res.end(),cmp);
    for (auto node:res) {
        // cout<<node.first<<" "<<node.second<<endl;
        cout<<node.first;
    }

}

//https://codefun2000.com/p/P2355 注意审题

void read(map<unsigned ll,string>&mp,unsigned ll len,unsigned ll add) {
    if (mp.count(add)) {
        string data = mp[add];
        if (len*2>data.size()) {
            data+=string(len*2-data.size(),'0');
        }else {
            data=data.substr(0,len*2);
        }
        cout<<data<<endl;
    }else {
        string s(len*2,'0');
        cout<<s<<endl;
    }
}
void write(map<unsigned ll,string>&mp,unsigned ll len,unsigned ll add,string &val) {
    string s;
    if (val.size()<len*2) {
        s=string (len*2-val.size(),'0');
        val+=s;
    }
    mp[add]= val;
}
void clear(map<unsigned ll,string>&mp) {
    mp.clear();
}
void hash6() {
    int n;
    cin>>n;
    map<unsigned ll,string> mp;
    getchar();
    while (n--) {
        string line;
        getline(cin,line);
        stringstream ss(line);
        if (line[0]=='W') {
            string add;
            //去掉Write
            getline(ss ,add,' ');
            getline(ss ,add,' ');
            add = add.substr(add.find('x')+1);
            string len ;
            getline( ss,len,' ');
            string val;
            getline(ss,val,' ');
            write(mp,stoull(len),stoull(add,nullptr,16),val);

        }else if (line[0]=='R') {
            string add;
            //去掉Read
            getline(ss ,add,' ');
            getline(ss ,add,' ');
            add = add.substr(add.find('x')+1);
            string len ;
            getline( ss,len,' ');
            read(mp,stoull(len),stoull(add,nullptr,16));

        }else {
            clear(mp);
        }
    }
}

//https://codefun2000.com/p/P2380 注意审题  两个hash  我这是直接一个一个找 其实可以用滑动窗口
string similar(string s) {
    string ans;
    for (int i=0;i<s.size();i++) {
        if (s[i]>='0'&&s[i]<='9') {
            continue;
        }else {
            ans+=s[i];
        }
    }
    return  ans;
}

void hash6() {
    int n;
    cin>>n;
    map<string,vector<int>> mp;
    map<string,vector<int>> mp2;
    while (n--) {
        string line;
        cin>>line;
        stringstream ss(line);
        string time;
        string log;
        getline(ss,time,':');
        getline(ss,log);
        bool insert=false;
        //找相同
        if (mp.count(log)) {
            sort(mp[log].begin(),mp[log].end());
            if (stoi(time) - mp[log][mp[log].size()-1]<10) {
                cout<<line<<endl;
                continue;
            }else {
                // mp[log].push_back(stoi(time));
                // continue;
                insert= true;
            }
        }else {
            // mp[log].push_back(stoi(time));
            // continue;
            insert=true;
        }
        //找相似
        string similog = similar(log);
        if (mp2.count(similog)) {
            int sum=0;
            for (auto content:mp2[similog]) {
                if (stoi(time)-content<100) {
                    sum++;
                }
            }
            if (sum>=9) {
                cout<<line<<endl;;
                continue;
            }else {
                // mp[log].push_back(stoi(time));
                // continue;
                insert= true;
            }
        }else {
            // mp[log].push_back(stoi(time));
            // continue;
            insert = true;
        }
        if (insert) {
            mp[log].push_back(stoi(time));
            mp2[similog].push_back(stoi(time));
        }


    }
}



int now=0,n;


struct  Node {
    int cnt,tim,key,value;
    Node(){}
    Node(int a,int b ,int c,int d) {
        cnt=a;
        tim=b;
        key=c;
        value=d;
    }
    bool operator <(const Node& node) const{
        return cnt==node.cnt?tim<node.tim:cnt<node.cnt;
    }
};
unordered_map<int,Node>mapp;
set<Node> S;
int get(int key) {
    if (n==0||mapp.find(key)==mapp.end()) {
        return -1;
    }
    Node cache = mapp[key];
    S.erase(cache);
    cache.cnt++;
    cache.tim+=++now;
    S.insert(cache);
    mapp[key]= cache;
    return cache.value;
}

void put(int key,int value) {
    if (n==0)return ;
    auto it =mapp.find(key);
    if (it ==mapp.end()) {
        if (mapp.size()==n) {
            mapp.erase(S.begin()->key);
            S.erase(S.begin());
        }
        Node cache =Node(1,++now,key,value);
        mapp[key] = cache;
        S.insert(cache);
    }else {
        Node cache =it->second;
        S.erase(cache);
        cache.cnt++;
        cache.tim=++now;
        cache.value=value;
        S.insert((cache));
        it->second=cache;
    }
}
//https://codefun2000.com/p/P2325  LRU 利用set o(1)获取要淘汰的 unordered map存储内容 o(1)查询是否在
void hash7() {
    string s;
    cin>>s;
    cin>>n;
    int x;
    while (cin>>s) {
        if (s[0]=='w') {
            int m;
            cin>>m;
            while (m--) {
                int a,b;
                cin>>a>>b;
                put(a,b);
            }
        }else if (s[0]=='r'){
            int a;
            cin>>a;
            get(a);
        }else {
            while (cin>>x) {
                if (mapp.count(x)) cout<<mapp[x].value;
                else cout<<-1<<endl;
            }
        }
    }


}